﻿// 247 亚特兰蒂斯 代码1.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
// 247. 亚特兰蒂斯.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//


/*

https://www.acwing.com/problem/content/249/

有几个古希腊书籍中包含了对传说中的亚特兰蒂斯岛的描述。

其中一些甚至包括岛屿部分地图。

但不幸的是，这些地图描述了亚特兰蒂斯的不同区域。

您的朋友 Bill 必须知道地图的总面积。

你自告奋勇写了一个计算这个总面积的程序。

输入格式
输入包含多组测试用例。

对于每组测试用例，第一行包含整数 n，表示总的地图数量。

接下来 n 行，描绘了每张地图，每行包含四个数字 x1,y1,x2,y2
（不一定是整数），(x1,y1)和 (x2,y2)分别是地图的左上角位置和右下角位置。

注意，坐标轴 x 轴从上向下延伸，y 轴从左向右延伸。

当输入用例 n=0 时，表示输入终止，该用例无需处理。

输出格式
每组测试用例输出两行。

第一行输出 Test case #k，其中 k 是测试用例的编号，从 1 开始。

第二行输出 Total explored area: a，其中 a 是总地图面积（即此测试用例中所有矩形的面积并，注意如果一片区域被多个地图包含，则在计算总面积时只计算一次）
，精确到小数点后两位数。

在每个测试用例后输出一个空行。

数据范围
1≤n≤10000,
0≤x1<x2≤100000,
0≤y1<y2≤100000

注意，本题 n 的范围上限加强至 10000。

输入样例：
2
10 10 20 20
15 15 25 25.5
0
输出样例：
Test case #1
Total explored area: 180.00

样例解释
样例所示地图覆盖区域如下图所示，两个矩形区域所覆盖的总面积，即为样例的解。

无标题.png
*/

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 100010;
int n;
vector<double> ys;

struct Segment {
	double x, y1, y2;
	int k;
	bool operator<(const Segment& t) const {
		return x < t.x;
	}
}seg[N*2];

struct Node {
	int l, r;
	//线段树节点tr[u]表示线段树Node区间[tr[u].l,tr[u].r] 维护离散化后的区间
	//--->[y_l,y_r+1]
	int cnt;
	double len;
}tr[N*2*4];

int find(double y) {
	//double坐标-->离散化后的坐标
	//返回区间中第一个>=y的数字的下标
	return lower_bound(ys.begin(), ys.end(), y) - ys.begin();
}


void build(int u, int l, int r) {
	if (l == r) tr[u] = { l,r,0,0 };
	else {
		tr[u] = { l,r };
		int mid = l + r >> 1;
		build(u << 1, l, mid);
		build(u << 1 | 1, mid + 1, r);
	}
}

void pushup(int u) {
	//如果当前节点被覆盖次数>0 直接计算当前节点的真实区间的长度
	//tr[u]表示离散化的区间 [tr[u].l,tr[u].r+1] 外面套一层ys表示double值
	if (tr[u].cnt) tr[u].len = ys[tr[u].r + 1] - ys[tr[u].l];

	//否则 如果当前节点被覆盖的次数==0[没覆盖满] 且不是叶子节点即孩子节点
	else if (tr[u].l != tr[u].r) //当前节点被覆盖的次数==0[没覆盖满] 通过孩子节点计算当前区间的len
	{
		tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
	}
	//当前节点被覆盖的次数==0[没覆盖满] 且是叶子节点
	else tr[u].len = 0; //是叶子节点 且节点len为0
}

void modify(int u, int l, int r, int k) {
	if (tr[u].l >= l && tr[u].r <= r) {
		tr[u].cnt += k;
		pushup(u);  //多了一步pushup操作 当前Node的cnt有变化 则也会影响当前Node的len 也会pushup
	}
	else {
		int mid = (tr[u].l + tr[u].r) >> 1;
		if (l <= mid) modify(u << 1, l, r, k);
		if (r > mid) modify(u << 1 | 1, l, r, k);
		pushup(u);
	}
}

int main() {
	int T = 1;
	while (scanf("%d", &n), n) {
		ys.clear();

		for (int i = 0, j = 0; i < n; i++) {
			double x1, y1, x2, y2;
			scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
			//读入2n个线段 seg里存的是double坐标
			seg[j++] = { x1,y1,y2,1 };
			seg[j++] = { x2,y1,y2,-1 };
			//所有y坐标存进ys里，待离散化
			ys.push_back(y1), ys.push_back(y2);
		}

		//对ys离散化
		sort(ys.begin(), ys.end());
		ys.erase(unique(ys.begin(), ys.end()),ys.end());

		//离散化后坐标2n个点 2n-1个区间
		//构建线段树 线段树的节点维护这些区间tr[i]-->[y_i,y_i+1]
		//所以线段树的节点个数与区间个数相同 2n-1
		//从1号开始构建线段树 对应的离散化后的坐标的取值范围是0~ys.size()-2 -->2n-1个
		build(1, 0, ys.size() - 2);

		//对线段按照x排序 从左往右
		sort(seg, seg + n * 2);

		double res = 0;
		for (int i = 0; i < n * 2; i++) {
			if (i > 0) res += tr[1].len * (seg[i].x - seg[i - 1].x);//计算答案
			modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].k);
			//这里一定要把double区间 变换到 线段树表示的区间 
			//线段树的节点 维护 离散化后的区间：tr[u] --> [tr[u].l,tr[u].r] --> [y_l, y_r + 1]
			//double的区间: seg[i].y1~seg[i].y2
			//离散化后的区间： find(seg[i].y1)~find(seg[i].y2)
			//线段树中的区间： find(seg[i].y1)~find(seg[i].y2)-1
		}

		printf("Test case #%d\n",T++);
		printf("Total explored area: %.2lf\n\n",res);
	}

	return 0;
}